public class IncreasingTriplet {

    public boolean increasingTriplet1(int[] nums) {
        return process(nums, 0, 0, Long.MIN_VALUE);
    }

    public boolean process(int[] nums, int i, int n, long last) {
        if (i == nums.length || n == 3) {
            if (n == 3) return true;
            return false;
        }
        if (nums[i] <= last) return process(nums, i + 1, n, last);
        return process(nums, i + 1, n, last) || process(nums, i + 1, n + 1, nums[i]);
    }

    public boolean increasingTriplet2(int[] nums) {
        int n = nums.length;
        int target = Integer.MAX_VALUE;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] >= target) continue;
            target = nums[i];
            int r = Integer.MAX_VALUE;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] > r) {
                    return true;
                } else if (nums[j] > nums[i] && nums[j] < r) {
                    r = nums[j];
                }
            }
        }
        return false;
    }

    //贪心
    public boolean increasingTriplet(int[] nums) {
        int m = nums.length;
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        for (int i = 1; i < m; i++) {
            if (nums[i] > second) return true;
            if (nums[i] > first) {
                second = nums[i];
            } else {
                first = nums[i];
            }
        }
        return false;
    }
}
